package com.mamingchao.basic.arraysort.quicksort;

import com.mamingchao.basic.arraysort.Sortable;

/**
 * 不同于经典单轴快排，双轴快排 选出两个轴, 数组分成三段，值小的轴 povit_little, 值大的轴 povit_large
 * 保证 数组最左边的是 < povit_little,中间是 ></=povit_little> povit_little <=povit_lager 最右边 ></=povit_large>
 * 选择数组的第一个和最后一个 作为数组的两个轴
 *
 * 思考：双轴比单轴 要快（理论上的，具体的需要需要自己验证一下）
 * 那么思考一个问题，如果 三轴呢，四轴 五轴呢？会不会更快？
 *
 * 我的答案：不管几轴，都需要递归去完成排序。那么单轴 执行一次完成排序的 数组长度是2（包括轴）
 * 双轴执行一次完成排序的 数组长度是3
 * 三轴执行一次完成排序的 数组长度是4
 * 四轴执行一次完成排序的 数组长度是5。。。
 * 所以轴多了，程序复杂度提高了（各种对比判断会多很多），但是执行一次完成排序的 数组长度是 却没有一同增长
 * 所以，双轴 比单轴到底快不快，这里也画一个问号，需要自己却 对比验证
 * Created by mamingchao on 2021/3/16.
 */
public class DualPovitQuickSort implements Sortable{


    /**
     *
     * @param arr 待排序数组
     * @param start 闭区间
     * @param end 闭区间
     */
    @Override
    public void sort(int[] arr,int start,int end) {
        if (end - start <2) {
            return;
        }
        //选择好
        int left_povit = 0;
        int right_povit = 0;

        if (arr[start] < arr[end]) {
            left_povit = start;
            right_povit = end;
        } else if (arr[start] < arr[end]){
            right_povit = start;
            left_povit = end;
        } else { //如果  left_povit == right_povit ,走单轴排序
            QuickSort1.sort(arr,start,end);
        }

        //从左向右遍历 游动的指针
        int left = start+1;
        //从右向左遍历 游动的指针
        int right = end - 1;
        // 小于左轴 最右边的元素索引
        int littleBound = start;
        // 大于右轴 最左边的元素索引
        int largeBound = end;

        while (left < right) {
            while (arr[left] < arr[left_povit] && left == littleBound +1 && left < right) {
                left ++;
                littleBound ++;
            }

            while (arr[right] > arr[right_povit] && right == largeBound -1 && left < right) {
                right --;
                largeBound --;
            }


            if (left == right) {
                break;
            }



            if (arr[left] > arr[right_povit] && arr[right] < arr[left_povit]) {
                swap(arr,left,right);
                swap(arr, right -- ,largeBound -- -1);
                swap(arr, left ++,littleBound ++ +1);
            } else if (arr[left] > arr[right_povit] && arr[right] >= arr[left_povit]) {
                swap(arr,left ++,right);
                swap(arr, right --,largeBound -- -1);
            } else if (arr[left] <= arr[right_povit] && arr[right] < arr[left_povit]) {
                swap(arr,left,right --);
                swap(arr, left ++ ,littleBound ++ +1);
            } else if (arr[left] <= arr[right_povit] && arr[right] >= arr[left_povit]) {
                left ++;
                right --;
            } else if (arr[left] < arr[left_povit]) {
                swap(arr,++littleBound,left ++);
            } else if (arr[right] > arr[right_povit]) {
                swap(arr,right--,--largeBound);
            }
        }

        if (right == left) {
            if (arr[left] < arr[left_povit]){
                swap(arr,littleBound ++ + 1,left);
            } else if (arr[right] > arr[right_povit]) {
                swap(arr,largeBound -- -1,right);
            }
        }
        swap(arr,littleBound,left_povit);
        swap(arr,largeBound,right_povit);

        if (littleBound - left_povit > 2) {
            sort(arr,left_povit,littleBound -1);
        }

        if (largeBound - littleBound > 3) {
            sort(arr,littleBound + 1, largeBound -1);
        }

        if (right_povit - largeBound > 2) {
            sort(arr,largeBound +1,right_povit);
        }

    }

}
